#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL p;
LL cal_sum(LL n,LL k)
{
	LL ret=0;
	if(k<0)
	{
		k=-k;
		ret+=(n+1)%p*(k%p)%p;
		k=0;
	}
	if(k>n)return 0;
	n-=k;
	if(n&1)ret=(ret+((n+1)/2%p*(n%p)%p))%p;
	else ret=(ret+(n/2%p*((n+1)%p)%p))%p;
	return ret;
}
LL cal(LL n,LL m,LL k)
{
	if(n<0||m<0)return 0;
	LL i=1;
	if(n<m)swap(n,m);
	while(i-1<=n)i<<=1;
	i>>=1;--i;
	if(m>=i) return ((((i+1)%p*cal_sum(i,k)%p)%p+((m-i+n-i)%p*cal_sum(i,k-i-1)%p)%p)%p+cal(n-i-1,m-i-1,k)%p)%p;
	else return (((m+1)%p*cal_sum(i,k)%p)%p+cal(n-i-1,m,k-i-1)%p)%p;
}
int main()
{
	LL T;
	scanf("%lld",&T);
	while(T--)
	{
		LL n,m,k;
		scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
		printf("%lld\n",cal(n-1,m-1,k));
	}
	return 0;
}
